#!/usr/bin/env python

#-------------------------------------------------------------------------------
rev_id = '$Id: $'
rev_author = '$Author: $'
rev_date = '$Date: $'
#-------------------------------------------------------------------------------
import os
import sys
import re

def usage():
    print "crc32 <data width> <output file name>"
    print "data width default = 8"
    print "output file name default = crc32_<data width>.v"

def optimize_xor(expr):
  '''
  Remove redundant xor terms in the expression.
  Terms which are repeated an even multiple times can be eliminated because
  a ^ a = 0 and 0 ^ b = b
  Terms which are repeated an odd multple times can be reduced because
  a ^ a ^ a ^ b = a ^ b
  Some illustrative examples:
  a ^ b ^ c ^ d ^ a => b ^ c ^ d (2 a terms cancel)
  a ^ b ^ c ^ d ^ a ^ a => a ^ b ^ c ^ d  (3 a terms reduce to a single a term)
  '''
  terms = expr.split("^")
  termCount = {}
  for t in terms:
    t=t.strip()
    if termCount.has_key(t):
      termCount[t] = termCount[t] + 1
    else:
      termCount[t] = 1

  opt_terms = []
  for t in termCount.keys():
    reducedCount = termCount[t] % 2
    if reducedCount == 1:
      opt_terms.append(t)

  opt_expr = ' ^ '.join(opt_terms)

  print '  --- orig - %d : ' % len(terms), terms
  print '  +++ redu - %d : ' % len(opt_terms), opt_terms

  if (len(terms)-len(opt_terms)) % 2 != 0:
    raise "Error: xor reduction algorithm must reduce by an even number of terms!"

  return opt_expr

# command line argument processing
#-------------------------------------------------------------------------------
help_arg = re.compile('(\-)+h', re.IGNORECASE)
for arg in sys.argv:
  if help_arg.match(arg):
    usage()
    sys.exit(0)

try:
    dataWidth = sys.argv[1]
    try:
        dwidth = int(dataWidth)
    except:
        print 'problem calculating dwidth'
        sys.exit(1)    
except:
    print 'Error: specify the data width argument'
    dwidth = 8

try:
    filename = sys.argv[2]
except:
    filename = 'crc32_data%d.v' % dwidth

# symbolic crc32 algorithm unrolling 
#-------------------------------------------------------------------------------
ofile = open(filename, 'w')
str = '// created by %s\n' % rev_id
ofile.write(str)

# CRC-32 polynomial is
# x^32 + x^26 + x^22 + x^16 + x^12 + x^11 + x^10 +
# x^8 + x^7 + x^5 + x^4 + x^2 + x + 1

# x^23 and x^27 and x^28 seem to be missing terms ...ps.

# symbolic names of state storage registers
a0 = "crc_state[0]"
a1 = "crc_state[1]"
a2 = "crc_state[2]"
a3 = "crc_state[3]"
a4 = "crc_state[4]"
a5 = "crc_state[5]"
a6 = "crc_state[6]"
a7 = "crc_state[7]"
a8 = "crc_state[8]"
a9 = "crc_state[9]"
a10 = "crc_state[10]"
a11 = "crc_state[11]"
a12 = "crc_state[12]"
a13 = "crc_state[13]"
a14 = "crc_state[14]"
a15 = "crc_state[15]"

a31 = "crc_state[31]"
a30 = "crc_state[30]"
a29 = "crc_state[29]"
a28 = "crc_state[28]"
a27 = "crc_state[27]"
a26 = "crc_state[26]"
a25 = "crc_state[25]"
a24 = "crc_state[24]"
a23 = "crc_state[23]"
a22 = "crc_state[22]"
a21 = "crc_state[21]"
a20 = "crc_state[20]"
a19 = "crc_state[19]"
a18 = "crc_state[18]"
a17 = "crc_state[17]"
a16 = "crc_state[16]"

ofile.write('\n')

# process input data symbols sequentially over the data width number 
# of iterations and construct symbolic expressions

for i in range(0,dwidth):
  data_index = dwidth - i;
  din = "data_in[%d]" % data_index
  feedback = a31 + " ^ " + din
  a31 = a30
  a30 = a29
  a29 = a28
  a28 = a27
  a27 = a26
  a26 = a25 + " ^ " + feedback
  a25 = a24
  a24 = a23
  a23 = a22 + " ^ " + feedback
  a22 = a21 + " ^ " + feedback
  a21 = a20
  a20 = a19
  a19 = a18
  a18 = a17
  a17 = a16
  a16 = a15 + " ^ " + feedback
  a15 = a14
  a14 = a13
  a13 = a12
  a12 = a11 + " ^ " + feedback
  a11 = a10 + " ^ " + feedback
  a10 = a9 + " ^ " + feedback
  a9 = a8
  a8 = a7 + " ^ " + feedback
  a7 = a6 + " ^ " + feedback
  a6 = a5
  a5 = a4 + " ^ " + feedback
  a4 = a3 + " ^ " + feedback
  a3 = a2
  a2 = a1 + " ^ " + feedback
  a1 = a0 + " ^ " + feedback 
  a0 = feedback
  print "debug -- cycle %d: \n" % i, a1

expr_list = [a0, a1, a2, a3, a4, a5, a6, a7, a8, a9,
a10, a11, a12, a13, a14, a15, a16, a17, a18, a19, 
a20, a21, a22, a23, a24, a25, a26, a27, a28, a29, 
a30]

#### TODO - put expr_list into a dictionary - explicit expr_label: expression

opt_expr_list = []
for expr in expr_list:
  opt_expr = optimize_xor(expr)
  opt_expr_list.append(optimize_xor(expr))

for expr in opt_expr_list:
  print '-----------------------------\n', expr

output_lines = []

str = "module crc32_data%d (crc_state, data_in, nextcrc_state)" % dwidth
output_lines.append(str)
str = ""
output_lines.append(str)
str = "input [31:0]                    crc_state"
output_lines.append(str)
str = "input [%d:0]                     data_in" % dwidth
output_lines.append(str)
str = ""
output_lines.append(str)
str = "output [31:0]                    nextcrc_state"
output_lines.append(str)
str = "reg [31:0]                       nextcrc_state"
output_lines.append(str)
str = ""
output_lines.append(str)
str = "always @(crc_state or data_in)"
output_lines.append(str)
str = "begin"
output_lines.append(str)

### todo
str = "  nextcrc_state[31] = %s" % a31
str = "  nextcrc_state[30] = %s" % a30
str = "  nextcrc_state[29] = %s" % a29
str = "  nextcrc_state[28] = %s" % a28
str = "  nextcrc_state[27] = %s" % a27
str = "  nextcrc_state[26] = %s" % a26
str = "  nextcrc_state[25] = %s" % a25
str = "  nextcrc_state[24] = %s" % a24
str = "  nextcrc_state[23] = %s" % a23
str = "  nextcrc_state[22] = %s" % a22
str = "  nextcrc_state[21] = %s" % a21
str = "  nextcrc_state[20] = %s" % a20
str = "  nextcrc_state[19] = %s" % a19
str = "  nextcrc_state[18] = %s" % a18
str = "  nextcrc_state[17] = %s" % a17
str = "  nextcrc_state[16] = %s" % a16
str = "  nextcrc_state[15] = %s" % a15
str = "  nextcrc_state[14] = %s" % a14
str = "  nextcrc_state[13] = %s" % a13
str = "  nextcrc_state[12] = %s" % a12
str = "  nextcrc_state[11] = %s" % a11
str = "  nextcrc_state[10] = %s" % a10
str = "  nextcrc_state[9] = %s"  % a9
str = "  nextcrc_state[8] = %s"  % a8
str = "  nextcrc_state[7] = %s"  % a7
str = "  nextcrc_state[6] = %s"  % a6
str = "  nextcrc_state[5] = %s"  % a5
str = "  nextcrc_state[4] = %s"  % a4
str = "  nextcrc_state[3] = %s"  % a3
str = "  nextcrc_state[2] = %s"  % a2
str = "  nextcrc_state[1] = %s"  % a1
str = "  nextcrc_state[0] = %s"  % a0

str = "end"
output_lines.append(str)
str = "endmodule"
output_lines.append(str)

output_str = '\n'.join(output_lines)
ofile.write(output_str)
ofile.close()

